/**
 * 
 */
package calculation;

import java.util.Map;
import java.util.HashMap;

import utils.CreateUtils;

/**
 * @author Michael
 *
 */
public class LineCrossingMostPoints {

	public static class Point {
		public double x;
		public double y;
	}
	
	public static class Line {
		public boolean isVertical;
		public double slope;
		public double intercept;
	}
	
	public static Line findLine(Point[] points) {
		assert (points != null);
		assert (points.length > 1);
		
		int maxPoints = 0;
		Line line = new Line();
		for (int i = 0; i < points.length -1; ++i) {
			Point p1 = points[i];
			int verticalPoint = 0;
			Map<Double, Integer> slopes = new HashMap<Double, Integer>();
			for (int j = i + 1; j < points.length; ++j) {
				Point p2 = points[j];
				if (p1.x == p2.x) {
					verticalPoint++;
					if (verticalPoint > maxPoints) {
						line.isVertical = true;
						line.slope = Double.NaN;
						line.intercept = p1.x;
					}
				}
				else {
					double slope = (p2.y - p1.y) / (p2.x - p1.x);
					if (slopes.containsKey(slope)) {
						slopes.put(slope, slopes.get(slope) + 1);
					}
					else {
						slopes.put(slope, 1);
					}
					if (slopes.get(slope) > maxPoints) {
						maxPoints = slopes.get(slope);
						line.isVertical = false;
						line.slope = slope;
						line.intercept = p1.y - p1.x * slope;
					}
				}
			}
		}
		
		return line;
	}
	
	/**
	 * 
	 */
	public LineCrossingMostPoints() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int n = CreateUtils.randNonNegInt(100);
		Point[] points = new Point[n];
		for (int i = 0; i < n; i++) {
			points[i] = new Point();
			points[i].x = CreateUtils.randReal(100);
			points[i].y = CreateUtils.randReal(100);
			System.out.print("(" + points[i].x + "," + points[i].y + ") ");
		}
		Line l = findLine(points);
		System.out.println("\nline slope: " + l.slope + " intercept: "
				+ l.intercept);

	}

}
